package com.gxc.tree;

/**
 * 小Q正在给一条长度为n的道路设计路灯安置方案。
 * 为了让问题更简单,小Q把道路视为n个方格需要照亮的地方用'.'表示，不需要照亮的障碍物格子用'X'表示。
 * 小Q现在要在道路上设置一些路灯，对于安置在pos位置的路灯，这盏路灯可以照亮pos - 1，pos，pos + 1这三个位置。
 * 小Q希望能安置尽量少的路灯照亮所有'.'区域，希望你能帮他计算一下最少需要多少盏路灯。
 * 输入描述:输入的第一行包含一个正整数t(1 <= t 1000)，表示测试用例数接下来每两行一个测试数据，
 * 第一行一个正整数n(1 <= n <= 1000)表示道路的长度。
 * 第二行一个字符串s表示道路的构造,只包含'.'和'X'。
 * 输出描述:
 * 对于每个测试用例，输出一个正整数表示最少需要多少盏路灯。
 *
 * 解法：
 * 贪心：
 * 从i位置尝试，保证i-1之前的位置都被点亮或是障碍物
 * 除了.X 类型，必须在第一个.位置放路灯
 * .......X  都是在第二个.位置放一盏路灯
 */
public class StreetLamp {

    public static void main(String[] args) {
        int size = 1000;
        for (int i = 0; i < size; i++) {
            String str = randomStr();
            if (process(str)!=process2(str)) {
                System.out.println(str);
                System.out.println("算法错误");
                break;
            }
        }

        String street = "....X";
        System.out.println(process(street));
    }

    public static int process(String street) {
        if (street == null || "".equals(street)) return 0;

        int sum = 0;
        char[] chars = street.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == 'X') {
                continue;
            } else {
                if (i+1<chars.length && chars[i+1] == 'X') {
                    sum++;
                    i++;
                } else {
                    sum++;
                    i+=2;
                }
            }
        }
        return sum;
    }

    public static int process2(String street) {
        if (street == null || "".equals(street)) return 0;

        int sum = 0;
        char[] chars = street.toCharArray();
        int i = 0;
        while (i<chars.length) {
            if (chars[i] == 'X') i++;
            else {
                sum++;
                if (i+1 < chars.length && chars[i+1] == 'X') {
                    i+=2;
                } else {
                    i+=3;
                }
            }
        }
        return sum;
    }

    private static String randomStr() {
        int length = (int) (Math.random()*100);
        StringBuffer buffer = new StringBuffer();
        for (int i = 0; i < length; i++) {
            int r = (int) (Math.random()*20);
            if (r<10) buffer.append(".");
            else buffer.append("X");
        }
        return buffer.toString();
    }

}
